package com.jonlandrum.collections.BinarySearchTree;

import java.util.NoSuchElementException;

public class LinkedBinarySearchTree<T extends Comparable<T>> implements BinarySearchTree<T> {
    private BinarySearchNode<T> root = null;

    /**
     * Constructs an empty BinarySearchTree.
     */
    public LinkedBinarySearchTree() {
    }

    /**
     * Constructs a new BinarySearchTree with the given node set as the root element.
     *
     * @param node The node to set as this tree's root element
     */
    public LinkedBinarySearchTree(BinarySearchNode<T> node) {
        root = node;
    }

    /**
     * Returns the root node of this tree.
     *
     * @return The root node of this tree
     */
    public BinarySearchNode<T> getRoot() {
        return root;
    }

    /**
     * Sets the root node of this tree to the node parameter.
     *
     * @param node The node to be set as this tree's root node
     */
    public void setRoot(BinarySearchNode<T> node) {
        root = node;
    }

    /**
     * Sets the root node of this tree to null.
     */
    public void setRoot() {
        root = null;
    }

    /**
     * Returns true if the root node of this tree is not null.
     *
     * @return True if the root node of this tree is not null
     */
    public boolean hasRoot() {
        return root != null;
    }

    /**
     * Inserts a new data element into this tree.
     *
     * @param data The data element to insert into this tree
     */
    public BinarySearchNode<T> insert(T data) {
        return this.insert(new LinkedBinarySearchNode<>(data));
    }

    /**
     * Inserts a new node into this tree.
     *
     * @param node The node to insert into this tree
     */
    public BinarySearchNode<T> insert(BinarySearchNode<T> node) {
        if (!hasRoot()) {
            setRoot(node);
        } else {
            LinkedBinarySearchNode<T> insertionPoint = (LinkedBinarySearchNode<T>) find(node);
            if (insertionPoint.compareTo(node) > 0) {
                if (insertionPoint.hasLeft()) {
                    node.setLeft(insertionPoint.getLeft());
                    insertionPoint.getLeft().setParent(node);
                }
                insertionPoint.setLeft(node);
                node.setParent(insertionPoint);
            } else {
                if (insertionPoint.hasRight()) {
                    node.setRight(insertionPoint.getRight());
                    insertionPoint.getRight().setParent(node);
                }
                insertionPoint.setRight(node);
                node.setParent(insertionPoint);
            }
        }
        return node;
    }

    /**
     * Deletes a data element from this tree.
     *
     * @param data The data element to be removed from this tree
     * @return The replacement of the data element removed from this tree
     */
    public BinarySearchNode<T> delete(T data) {
        return this.delete(new LinkedBinarySearchNode<>(data));
    }

    /**
     * Deletes a node from this tree.
     *
     * @param node The node to be removed from this tree
     * @return The replacement of the node removed from this tree
     */
    public BinarySearchNode<T> delete(BinarySearchNode<T> node) {
        LinkedBinarySearchNode<T> target = (LinkedBinarySearchNode<T>) search(node);
        LinkedBinarySearchNode<T> replacement = (LinkedBinarySearchNode<T>) target.getReplacement();
        if (replacement.hasData()) {
            if (replacement.hasChild()) {
                if (replacement.isLeft()) {
                    if (replacement.hasRight()) {
                        replacement.getParent().setLeft(replacement.getRight());
                    } else {
                        replacement.getParent().setLeft(replacement.getLeft());
                    }
                    replacement.getParent().getLeft().setParent(replacement.getParent());
                } else {
                    if (replacement.hasLeft()) {
                        replacement.getParent().setRight(replacement.getLeft());
                    } else {
                        replacement.getParent().setRight(replacement.getRight());
                    }
                    replacement.getParent().getRight().setParent(replacement.getParent());
                }
                replacement.setLeft();
                replacement.setRight();
            } else {
                if (replacement.isLeft()) {
                    replacement.getParent().setLeft();
                } else {
                    replacement.getParent().setRight();
                }
            }
            if (target.hasLeft()) {
                replacement.setLeft(target.getLeft());
                replacement.getLeft().setParent(replacement);
            }
            if (target.hasRight()) {
                replacement.setRight(target.getRight());
                replacement.getRight().setParent(replacement);
            }
            if (target.hasParent()) {
                if (target.isLeft()) {
                    target.getParent().setLeft(replacement);
                } else {
                    target.getParent().setRight(replacement);
                }
                replacement.setParent(target.getParent());
            } else {
                this.setRoot(replacement);
                replacement.setParent();
            }
        } else {
            if (target.hasParent()) {
                if (target.isLeft()) {
                    target.getParent().setLeft();
                } else {
                    target.getParent().setRight();
                }
            } else {
                setRoot();
            }
        }
        return replacement;
    }

    /**
     * Searches for a specific data element in this tree.
     *
     * @param data The data element of the same value as the node searched for
     * @return The node searched for
     */
    public BinarySearchNode<T> search(T data) {
        return this.search(new LinkedBinarySearchNode<>(data));
    }

    /**
     * Searches for a specific node in this tree.
     *
     * @param node The data element of the same value as the node searched for
     * @return The node searched for
     * @throws NoSuchElementException if the desired node is not in this tree
     */
    public BinarySearchNode<T> search(BinarySearchNode<T> node) throws NoSuchElementException {
        LinkedBinarySearchNode<T> result = (LinkedBinarySearchNode<T>) find(node);
        if (!hasRoot() ||
                result == null ||
                result.compareTo(node) != 0) {
            throw new NoSuchElementException("No Such Element");
        }
        return result;
    }

    private BinarySearchNode<T> find(BinarySearchNode<T> node) {
        LinkedBinarySearchNode<T> temp = (LinkedBinarySearchNode<T>) getRoot();
        if (hasRoot() && temp.hasData()) {
            while (temp.compareTo(node) != 0) {
                if (temp.compareTo(node) > 0) {
                    if (temp.hasLeft()) {
                        temp = (LinkedBinarySearchNode<T>) temp.getLeft();
                    } else {
                        break;
                    }
                } else {
                    if (temp.hasRight()) {
                        temp = (LinkedBinarySearchNode<T>) temp.getRight();
                    } else {
                        break;
                    }
                }
            }
        }
        return temp;
    }
}
